#-*- coding:utf-8 -*-
from copy import deepcopy
from random import randint

def removeAll(l, e):
	r = range(len(l))
	r.reverse()
	for i in r:
		if l[i]==e:
			del l[i]

def peutRetirer(i, bag, jeu):
	for mik in jeu:
		if mik[0] == i:
			return False
	return True

def estJouable(bag, jeu):
	ordre = []
	cpBag = bag[:]
	cpJeu = deepcopy(jeu)
	print "entré", bag, jeu
	if (not bag) or (not jeu):
		print "cas de base"
		return True
	else:
		for b in bag:
			if peutRetirer(b, cpBag, cpJeu):
				print "peut retirer", b
				cpBag.remove(b)
				cpJeu = [x for x in cpJeu if x[1]!=b]
				print "appel récursif"
				return estJouable(cpBag, cpJeu)
		return False

def creerEnchevetrements(bag, i, maxi):
	n = randint(0,maxi)
	ret = []
	for i in range(n):
		choix = randint(0, len(bag)-2)
		if choix==i:
			choix += 1
		ret.append([choix, i])
	return ret
	
def mikado(bag):
	jeu = []
	maxi = len(bag)
	tmp = []
	for mik in bag:
		while (len(tmp)==0) or (estJouable(bag, tmp)==False):
			tmp = jeu + creerEnchevetrements(bag, mik, maxi)
		jeu = tmp[:]
	return jeu

def quelOrdre(bag, jeu):
	ordre = []
	cpBag = bag[:]
	cpJeu = deepcopy(jeu)
	print bag, jeu
	if bag:
		for b in bag:
			if peutRetirer(b, cpBag, cpJeu):
				cpBag.remove(b)
				cpJeu = [x for x in cpJeu if x[1]!=b]
				ordre.append(b)
				return ordre + quelOrdre(cpBag, cpJeu)
	else:
		return ordre

def quelOrdre_beurk(bag, jeu, ordre):
	#cas de base
	if len(jeu) == 0:
		return bag
	else:
		#histoire de ne pas les massacrer
		cpBag = bag[:]
		cpJeu = deepcopy(jeu) #pour ne pas devenir FOU
		#énumérer les baguettes potentiellement indépendantes
		indep = [x[1] for x in jeu]
		#éliminer de cette liste les baguettes dépendantes
		for mik in jeu:
			if mik[0] in indep:
				removeAll(indep, mik[0])
		#supprimer les baguettes indépendantes
		if indep: #façon propre en Python de tester la longueur d'une liste
			for x in indep:
				if x in cpBag:
					ordre.append(x)
					cpBag.remove(x)
			#supprimer les contraintes devenues inutiles
			#astuce : pour ne pas décaler les indices, 
			#on le fait dans le sens inverse.
			rg = range(len(jeu))
			rg.reverse()
			for i in rg:
				if jeu[i][1] in indep:
					#il se pourrait qu'on puisse virer direct' la baguette
					if peutRetirer(jeu[i][0], cpBag, cpJeu):
						ordre.append(jeu[i][0])
						cpBag.remove(jeu[i][0])
					del cpJeu[i]
			#appel récursif
			return quelOrdre(cpBag, cpJeu, ordre)

		else:
			#on ne peut plus en retirer !
			return None



bag = range(4)
jeu = [[0, 1], [0, 2], [3, 2]]
#jeu = [[0, 1], [1, 0]]
print estJouable(bag, jeu)
#print creerEnchevetrements(bag, 0, 5)
#print quelOrdre(bag, jeu) 
